
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        if (A == null || A.length < 1) {
            return -1;
        }
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid] > val) {
                high = mid - 1;
            } else if (A[mid] < val) {
                low = mid + 1;
            } else {
                // 1
                while(mid > 0 && mid < n && A[mid-1] == val){
                    mid--;
                }
                return mid;
            }
        }
        return -1;
    }
}